TNotes.leetcode

Appearance

⏰0987. 二叉树的垂序遍历【困难】

0987. 二叉树的垂序遍历【困难】 ​

1. 📝 题目描述 ​

给你二叉树的根结点 root，请你设计算法计算二叉树的垂序遍历序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1)。树的根结点位于 (0, 0)。

二叉树的垂序遍历从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的垂序遍历序列。

示例 1：

img

txt
输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]

解释：
列 -1 ：只有结点 9 在此列中。
列  0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
列  1 ：只有结点 20 在此列中。
列  2 ：只有结点 7 在此列中。

示例 2：

img

txt
输入：root = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]

解释：
列 -2 ：只有结点 4 在此列中。
列 -1 ：只有结点 2 在此列中。
列  0 ：结点 1 、5 和 6 都在此列中。
          1 在上面，所以它出现在前面。
          5 和 6 位置都是 (2, 0)，所以按值从小到大排序，5 在 6 的前面。
列  1 ：只有结点 3 在此列中。
列  2 ：只有结点 7 在此列中。

示例 3：

img

txt
输入：root = [1,2,3,4,6,5,7]
输出：[[4],[2],[1,5,6],[3],[7]]

解释：
这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。

提示：

  • 树中结点数目总数在范围 [1, 1000] 内
  • 0 <= Node.val <= 1000

2. 🎯 s.1 - DFS + 排序 ​

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalTraversal = function (root) {
  const nodes = [] // 存储所有节点信息 [col, row, val]

  // DFS 遍历，记录每个节点的坐标和值
  const dfs = (node, row, col) => {
    if (!node) return
    nodes.push([col, row, node.val])
    dfs(node.left, row + 1, col - 1)
    dfs(node.right, row + 1, col + 1)
  }

  dfs(root, 0, 0)

  // 排序：先按列，再按行，最后按值
  nodes.sort((a, b) => {
    if (a[0] !== b[0]) return a[0] - b[0] // 按列排序
    if (a[1] !== b[1]) return a[1] - b[1] // 按行排序
    return a[2] - b[2] // 按值排序
  })

  // 按列分组
  const result = []
  let prevCol = null
  for (const [col, row, val] of nodes) {
    if (col !== prevCol) {
      result.push([])
      prevCol = col
    }
    result[result.length - 1].push(val)
  }

  return result
}
  • 时间复杂度：O(nlog⁡n)，其中 n 是树中节点数量，主要开销在排序上
  • 空间复杂度：O(n)，存储所有节点信息的数组

算法思路：

  • DFS 遍历：深度优先遍历二叉树，记录每个节点的列坐标 col、行坐标 row 和节点值 val
  • 坐标定义：根节点位于 (0, 0)，左子节点为 (row+1, col-1)，右子节点为 (row+1, col+1)
  • 三级排序：按列优先、同列按行优先、同行同列按值从小到大排序
  • 分组输出：遍历排序后的节点列表，按列分组，将同列的节点值收集到一个数组中
  • 结果构建：当列号改变时创建新的分组，将节点值添加到对应的列分组中